package com.code4j.tree;

import java.util.HashMap;
import java.util.Map;
import java.util.Observable;
import java.util.Observer;
import java.util.Stack;

// BinaryTree.java 
public class BinaryTree {
	// Root node pointer. Will be null for an empty tree.
	private Node root;

	/*
	 * --Node-- The binary tree is built using this nested node class. Each node
	 * stores one data element, and has left and right sub-tree pointer which
	 * may be null. The node is a "dumb" nested class -- we just use it for
	 * storage; it does not have any methods.
	 */
	public static class Node {
		Node left;
		Node right;
		int data;
		boolean visit;

		Node(int newData) {
			left = null;
			right = null;
			data = newData;
		}

		public Node getLeft() {
			return left;
		}

		public void setLeft(Node left) {
			this.left = left;
		}

		public Node getRight() {
			return right;
		}

		public int getData() {
			return data;
		}

		@Override
		public String toString() {
			return "Node [left=" + left + ", right=" + right + ", data=" + data
					+ "]";
		}

		public void free() {
			data = 0;
			left = null;
			right = null;
		}
	}

	/**
	 * Creates an empty binary tree -- a null root pointer.
	 */
	public BinaryTree() {
		root = null;
	}

	/**
	 * Returns true if the given target is in the binary tree. Uses a recursive
	 * helper.
	 */
	public boolean lookup(int data) {
		return (lookup(root, data));
	}

	/**
	 * Recursive lookup -- given a node, recur down searching for the given
	 * data.
	 */
	private boolean lookup(Node node, int data) {
		if (node == null) {
			return (false);
		}

		if (data == node.data) {
			return (true);
		} else if (data < node.data) {
			return (lookup(node.left, data));
		} else {
			return (lookup(node.right, data));
		}
	}

	/**
	 * Inserts the given data into the binary tree. Uses a recursive helper.
	 */
	public void insert(int data) {
		root = insert(root, data);
	}

	/**
	 * Recursive insert -- given a node pointer, recur down and insert the given
	 * data into the tree. Returns the new node pointer (the standard way to
	 * communicate a changed pointer back to the caller).
	 */
	private Node insert(Node node, int data) {
		if (node == null) {
			node = new Node(data);
		} else {
			if (data <= node.data) {
				node.left = insert(node.left, data);
			} else {
				node.right = insert(node.right, data);
			}
		}

		return (node); // in any case, return the new pointer to the caller
	}

	public Node getRoot() {
		return root;
	}

	public void setRoot(Node root) {
		this.root = root;
	}

	/************ observable ***************/
	class MyObservable extends Observable {

		@Override
		public synchronized void setChanged() {
			super.setChanged();
		}

		@Override
		public synchronized void clearChanged() {
			super.clearChanged();
		}

	}

	MyObservable observable = new MyObservable();

	public void addObserver(Observer o) {
		observable.addObserver(o);
	}

	public void deleteObserver(Observer o) {
		observable.deleteObserver(o);
	}

	public void notifyObservers(Object arg) {
		observable.setChanged();
		observable.notifyObservers(arg);
		observable.clearChanged();
	}

	/************ observable ***************/

	/**
	 * 更新整棵树
	 */
	public void refreshTree() {
		notifyObservers(this);
	}

	public void clearAll() {
		clearAll(root);
		root = null;
		refreshTree();
	}

	public void clearAll(Node root) {
		if (root != null) {
			clearAll(root.left);
			clearAll(root.right);
			root.free();
		}
	}

	public void preOrder() {
		notifyObservers("clear");
		preOrder(root);
	}

	public void preOrder(Node root) {
		if (root == null)
			return;
		notifyObservers(root);
		preOrder(root.left);
		preOrder(root.right);
	}

	public void height() {
		notifyObservers("clear");
		notifyObservers(height(root) + "");
	}

	public int height(Node root) {
		if (root == null)
			return 0;
		int height1 = height(root.left);
		int height2 = height(root.right);
		return height1 > height2 ? height1 + 1 : height2 + 1;

	}

	public void dfs(Node root) {
		Stack<Node> stack = new Stack<Node>();
		if (root == null)
			return;
		// Node temp = root;
		// while (temp != null || !stack.isEmpty()) {
		//
		// while (temp != null) {
		// notifyObservers(temp);
		// stack.push(temp);
		// temp = temp.left;
		// }
		// if (!stack.isEmpty()) {
		// temp = stack.pop();
		// //notifyObservers(temp);
		// temp = temp.right;
		// }
		// }

		stack.push(root);
		while (!stack.isEmpty()) {
			Node node = stack.peek();
			if (node.left != null && !node.left.visit) {
				stack.push(node.left);
			} else if (node.right != null && !node.right.visit) {
				stack.push(node.right);
			} else {
				stack.pop();
				node.visit = true;
				notifyObservers(node);
			}
		}
	}

	public void dfs() {
		notifyObservers("clear");
		dfs(root);
	}
}
